package com.zjsru.leetcode75.level1;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: cookLee
 * @Date: 2024-01-01
 * 重新规划路线
 * 路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。
 */
public class MinReorder {

    /**
     * 主
     * \
     * 输入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
     * 输出：3
     * 解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。
     * \
     * 输入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
     * 输出：2
     * 解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MinReorder minReorder = new MinReorder();
        int n = 6;
        int[][] connections = new int[][]{{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
        System.out.println(minReorder.minReorder(n, connections));
    }

    /**
     * 最小重新排序
     * dfs
     * @param n           n
     * @param connections 连接
     * @return int
     */
    public int minReorder(int n, int[][] connections) {
        List<int[]>[] list = new List[n];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
        for (int[] edge : connections) {
            //对于边(a, b)，在list[a]中添加(b, 1)，表示从节点a到节点b的有向边需要重新排序。同时，在list[b]中添加(a, 0)，表示从节点b到节点a的有向边不需要重新排序。
            list[edge[0]].add(new int[]{edge[1], 1});
            list[edge[1]].add(new int[]{edge[0], 0});
        }
        return this.dfs(0, -1, list);
    }

    /**
     * dfs
     *
     * @param list    列表
     * @param current 电流
     * @param parent  父母
     * @return int
     */
    private int dfs(int current, int parent, List<int[]>[] list) {
        int res = 0;
        for (int[] edge : list[current]) {
            //表示已经访问过该节点，跳过
            if (edge[0] == parent) {
                continue;
            }
            res += edge[1] + this.dfs(edge[0], current, list);
        }
        return res;
    }

}
